Caminhos e Ciclos

Tópicos

• Caminhos
  • Passeio
  • Caminho
• Ciclos
  • Trilha/Trajeto
  • Circuito/Trajeto fechado
  • Ciclo
  • Exemplos

Caminhos

Passeio

• Um passeio em um grafo G = (V, E) consiste de uma sequência finita alternada de vértices e arestas.
• Um passeio com k vértices possui k-1 arestas.

Caminho

• Um caminho em um grafo G = (V, E) é um passeio em que todos os seus vértices são distintos.

0-2-7-3-6 é um caminho simples

Ciclos

Trilha/Trajeto

• É um passeio em que todas as suas arestas são distintas.

Circuito/Trajeto fechado

• É um trajeto em que o vértice inicial e o vértice final são iguais.

Ciclo

• É um circuito em que todos os vértices são distintos (exceto o primeiro e o último).

OBS: grafo acíclico é aquele que não possui ciclos

Exemplos

Exemplo 1:

A sequência {c,a,d,e,c}:

1. É uma trilha
2. É um circuito
3. É um ciclo

Exemplo 2:

• Possíveis caminhos:
  1. E → B → D→E
  2. A → C → D → E → B → A
  3. B → D → E → B → C
  4. A → B → C → D → B → A